package leetcode.code1368;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

	int[] xx = new int[] { 0, 0, 0, 1, -1 };
	int[] yy = new int[] { 0, 1, -1, 0, 0 };
	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };
	int[][] grid;
	int m, n;
	Integer[][] been;
	Queue<int[]> queue;

	public int minCost(int[][] grid) {
		this.grid = grid;
		m = grid.length;
		n = grid[0].length;
		been = new Integer[m][n];
		queue = new LinkedList<>();
		dfs(0, 0, 0);
//		if (been[m - 1][n - 1] != null) {
//			return been[m - 1][n - 1];
//		}
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int x = cur[0], y = cur[1], z = ++cur[2];
			for (int i = 0; i < 8; i += 2) {
				int nextx = x + d[i], nexty = y + d[i + 1];
				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && been[nextx][nexty] == null) {
					dfs(nextx, nexty, z);
					if (been[m - 1][n - 1] != null) {
						return been[m - 1][n - 1];
					}
				}
			}
		}
		return 0;
	}

	private void dfs(int x, int y, int z) {
		if (been[x][y] != null) {
			return;
		}
		been[x][y] = z;
		queue.add(new int[] { x, y, z });
		int d = grid[x][y];
		int nextx = x + xx[d];
		int nexty = y + yy[d];
		if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && been[nextx][nexty] == null) {
			dfs(nextx, nexty, z);
		}
	}
}
